package me.zk.practice1.s;

/**
 * @author zhangkai
 * @date 2023/7/27 10:32
 */
public class LS109 {
    // 1 2 3 4 5
    // 2 3
    //3 5
    public TreeNode sortedListToBST(ListNode head) {

        return buildTree(head,null);
    }

    public TreeNode buildTree(ListNode left,ListNode right) {
        if (left == right) {
            return null;
        }
        ListNode node = getMid(left,right);
        TreeNode treeNode = new TreeNode();
        treeNode.val = node.val;
        treeNode.left = buildTree(left,node);
        treeNode.right = buildTree(node.next,right);

        return treeNode;
    }
    public ListNode getMid(ListNode left,ListNode right) {
        ListNode slow = left;
        ListNode fast = left;

        while (left != right && fast.next!=right) {
            slow = slow.next;
            fast = fast.next.next;

        }
        return slow;

    }

}
